package com.king.common.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.springframework.util.CollectionUtils;

import com.king.framework.base.service.TreeInterface;

public class TreeUtils {

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static  List<TreeInterface> buildTree(List<TreeInterface> list){
		List<TreeInterface> resultList = new ArrayList<TreeInterface>();
		Map<Long,List<TreeInterface>> childMap = new HashMap<>();
		
		List<TreeInterface> childList = null;
		Set<Long> idSet = new HashSet<>();
		for(TreeInterface obj : list){
			childList = childMap.get(obj.getParentid());
			if(childList == null){
				childList = new ArrayList<>();
			}
			childList.add(obj);
			childMap.put(obj.getParentid(), childList);
			idSet.add(obj.getId());
		}
		List<TreeInterface> rootList = new ArrayList<>();//顶层节点
		for(TreeInterface obj : list){
			if(!idSet.contains(obj.getParentid())){
				rootList.add(obj);
			}
		}
		for(TreeInterface obj : rootList){
			childList = childMap.get(obj.getId());
			if(CollectionUtils.isEmpty(childList)){
				continue;
			}
			obj.setChildren(childList);
			
			recursionChildren(obj, childMap);
			resultList.add(obj);
		}
		return resultList;
	}

	@SuppressWarnings("rawtypes")
	private static void recursionChildren(TreeInterface obj, Map<Long,List<TreeInterface>> childMap){
		List<TreeInterface> childList = childMap.get(obj.getId());
		if(CollectionUtils.isEmpty(childList)){
			return;
		}
		for(TreeInterface child : childList){
			recursionChildren(child, childMap);
		}
		obj.setChildren(childList);
	}
}
